home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / clean / sun3.lha / Sun3 / seqdemos / fsieve.icl < prev    next >
Text File  |  1992-08-07  |  1KB  |  52 lines
  1. MODULE fsieve;
  2.  
  3. <<
  4. The Fast Sieve of Eratosthenes.
  5.  
  6. A sequential and optimized version of the sieve of Eratosthenes.
  7. The program calculates a list of the first NrOfPrime primes.
  8. The result of the program is the NrOfPrimes'th prime.
  9.  
  10. Strictness annotations have been added because the strictness analyser
  11. is not able to deduce all strictness information. Removal of these !'s
  12. will make the program about 20% slower.
  13. >>
  14.  
  15. IMPORT deltaI, deltaR;
  16.  
  17. MACRO
  18.     NrOfPrimes -> 3000;
  19.     
  20. RULE
  21.  
  22. ==  The sieve algorithm: generate an infinite list of all primes.
  23.  
  24. ::  Primes -> [INT];
  25.     Primes -> pr:[5 | Sieve 7 4 pr];
  26.  
  27. ::  Sieve INT !INT [INT] -> [INT];
  28.     Sieve g i prs
  29.     -> [g | Sieve' g i prs]     , IF IsPrime prs g (RTOI (SQRT (ITOR g)))
  30.     -> Sieve (+ g i) (- 6 i) prs;
  31.  
  32. ::  Sieve' INT INT [INT] -> [INT];
  33.     Sieve' g i prs -> Sieve (+ g i) (- 6 i) prs;
  34.  
  35. ::  IsPrime [INT] !INT INT -> BOOL;
  36.     IsPrime [f|r] pr bd -> TRUE           , IF > f bd
  37.                         -> FALSE          , IF = (% pr f) 0
  38.                         -> IsPrime r pr bd;
  39.                                   
  40. ==  Select is used to get the NrOfPrimes'th prime from the infinite list.
  41.  
  42. ::  Select [x] INT -> x;
  43.     Select [f|r] 1 -> f;
  44.     Select [f|r] n -> Select r (-- n);
  45.  
  46.  
  47. <<  The Start rule: Select the NrOfPrimes'th prime from the list of primes
  48.     generated by Primes.
  49. >>
  50. ::  Start -> INT;
  51.     Start -> Select [2, 3 | Primes] NrOfPrimes;
  52.